import java.util.ArrayList;
import java.util.List;

public class Test2 {
    // 腐烂的橘子
    // https://leetcode.cn/problems/rotting-oranges/description/
    /**
     * 每一次都将腐烂的橘子的坐标存在列表中，然后每次遍历就将新腐烂的橘子放入列表中，并且移除已经腐烂的橘子
     */
    private int[] x = {-1,0,0,1};
    private int[] y = {0,-1,1,0};
    public int orangesRotting(int[][] grid) {
        int time = 0;
        int fresh = 0;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    fresh++;
                } else if (grid[i][j] == 2) {
                    list.add(new int[]{i,j});
                }
            }
        }
        while (list.size() > 0 && fresh > 0) {
            int size = list.size();
            for (int i = 0; i < size; i++) {
                int[] arr = list.remove(0);
                for (int j = 0; j < 4; j++) {
                    int newRow = arr[0] + x[j];
                    int newCol = arr[1] + y[j];
                    if (newRow >= 0 && newRow < grid.length
                            && newCol >= 0 && newCol < grid[0].length
                            && grid[newRow][newCol] == 1) {
                        grid[newRow][newCol] = 2;
                        list.add(new int[]{newRow,newCol});
                        fresh--;
                    }
                }
            }
            time++;
        }
        return fresh == 0 ? time : -1;

    }

    public static void main(String[] args) {
        Test2 t = new Test2();
        int[][] grid = {{2,1,1},{1,1,0},{0,1,1}};
        System.out.println(t.orangesRotting(grid));
    }
}
